// Created by WXX on 2022/1/7 14:44
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

/**
 * 执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
 * 内存消耗：6.3 MB, 在所有 C++ 提交中击败了34.85%的用户
 */
class Solution {
public:
    unordered_map<string, char> wp;
    unordered_map<char, string> pw;

    bool wordPatternMatch(string pattern, string s) {
        return dfs(pattern, 0, s, 0);
    }

    bool dfs(string &pattern, int x, string &s, int y) {

        if (x == pattern.size() && y == s.size()) return true;
        if (x == pattern.size() || y == s.size()) return false;

        if (pattern.size() - x > s.size() - y) return false;  // 剪枝

        char a = pattern[x];
        for (int i = y; i < s.size(); i++) {
            string b = s.substr(y, i - y + 1);
            if (pw.count(a) && pw[a] == b) {
                if (dfs(pattern, x + 1, s, i + 1)) return true;
            } else if (!pw.count(a)) {
                if (wp.count(b)) continue;  // 说明 b<->其他字母，此时不能建立 ab 之间的映射
                pw[a] = b, wp[b] = a;
                if (dfs(pattern, x + 1, s, i + 1)) return true;
                pw.erase(a), wp.erase(b);
            }
        }
        return false;
    }
};

int main() {

    cout << Solution().wordPatternMatch("abab", "redblueredblue") << endl;  // true

    return 0;
}
